package com.jacky.链表;

public class K个一组翻转链表_25 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1 || head == null || head.next == null) return head;
        //一开始当前节点就是头节点
        ListNode cur = head;
        //记录当前节点走了多少步
        int count = 1;
        //通过循环对head进行分组，k个一组
        while (count < k) {
            cur = cur.next;
            //如果传入链表小于k个，直接返回，不用翻转，也是递归的推出条件
            if (cur == null) return head;
            count++;
        }
        //把当前节点下一个节点，临时存起来，免得找不到
        ListNode tmp = cur.next;
        //当前节点下一个节点指向null
        cur.next = null;
        reverseList(head);
        head.next = reverseKGroup(tmp, k);
        return cur;
    }

    public static ListNode reverseList(ListNode head) {
        //定义前一个节点，把当前节点的的next指针，指向前一个节点，cur.next=pre
        ListNode pre = null;
        //一开始当前节点就是头节点
        ListNode cur = head;
        //遍历链表，循环条件是，当前不等于null
        while (cur != null) {
            //把当前节点的next先用临时节点先存起来，不然当前节点的next指向前一个节点之后，找不到原来的next节点，导致遍历不下去
            ListNode temp = cur.next;
            //当前节点的next指向前一个节点
            cur.next = pre;
            //前节点向右移动一位
            pre = cur;
            //当前节点也向前移动一位
            cur = temp;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = new ListNode(5);
        reverseKGroup(listNode1, 3);
    }

}
